/**
 * 
 */
package truerefactor.graph;

import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * DiGraph - Base class for a Directed Graph Abstract Data Structure
 * 
 * @author Isaac Griffith
 */
public abstract class DiGraph {

    /**
     * List of all the nodes in the graph
     */
    protected List<CodeNode> nodes;
    /**
     * Map of a List of Nodes containing all of the nodes dependent upon the
     * CodeNode indexing the List in the Map
     */
    protected Map<CodeNode, List<Edge>> adjacencies;
    /**
     * List of sink nodes of the graph. Where a sink node is a node which is not
     * a source end of any edge in the graph.
     */
    protected List<CodeNode> sinks;
    /**
     * List of source nodes of the graph. Where a source node is a node which is
     * not the destination end of any edge in the graph.
     */
    protected List<CodeNode> sources;

    /**
     * Returns a Edge (directed Edge) if one exists between the source node and
     * the destination node. If no such edge actually exists in the graph, then
     * null is returned.
     * 
     * @param source
     *            The from node, where the edge originates
     * @param destination
     *            The to node, where the edge ends.
     * @return Edge encapsulating the directional relationship between the
     *         source and destination nodes if such a relationship exists.
     */
    public abstract Edge getEdge(CodeNode source, CodeNode destination, EdgeType type);

    /**
     * Returns an Iterator for this graph which enumerates a sequence of nodes
     * using the edges linking nodes. As a requirement if a node is not
     * connected or if there are two subgraphs with in the graph which are not
     * connected, there is no guarantee as to the order of the nodes in both
     * subgraphs in sequence beyond the order maintained inside the subgraphs
     * themselves.
     * 
     * @return an iterator over this graph.
     */
    public abstract GraphIterator getIterator();

    /**
     * Returns all nodes known to exist within this Graph Structure.
     * 
     * @return List of CodeNodes in this Graph.
     */
    public abstract List<CodeNode> getNodes();

    /**
     * Inserts the provided Edge into this graph, if such edge does not already
     * exist.
     * 
     * @param edge
     *            Edge to be inserted.
     */
    public abstract void insert(Edge edge);

    /**
     * Returns the number of edges that exist in this graph
     * 
     * @return number of edges comprising this graph
     */
    public abstract int numberOfEdges();

    /**
     * Returns the number of Nodes contained in this graph.
     * 
     * @return number of nodes comprising this graph
     */
    public abstract int numberOfNodes();

    /**
     * Removes the specified node, if it exists in this graph, from this graph.
     * Upon remove all edges connecting nodes to the specified node, and edges
     * connecting from this node are simultaneously removed as well.
     * 
     * @param node
     *            CodeNode to be removed from this graph.
     */
    public abstract void remove(CodeNode node);

    /**
     * Removes the specified Edge, if such an edge connects the contained nodes
     * exists in this graph, from this graph.
     * 
     * @param edge
     *            Edge to be removed from this graph.
     */
    public abstract void remove(Edge edge);

    /**
     * Returns the CodeNode at the specified index in the adjacency list
     * 
     * @see DiGraph#indexOf(CodeNode)
     * @param index
     *            Index of the CodeNode to be retrieved
     * @return CodeNode with the specified index, if the index is not greater
     *         than the number of available nodes, or less than 0. Otherwise
     *         this method returns null.
     */
    public abstract CodeNode get(int index);

    /**
     * Returns a List of Nodes adjacent to the CodeNode specified.
     * 
     * @param node
     *            CodeNode whose adjacency list is required
     * @return Adjacency list for the specified node, if that node exists in the
     *         graph, or null, if it doesn't.
     */
    public abstract List<CodeNode> getAdjacencies(CodeNode node);

    /**
     * Returns the index in the adjacency list of the specified CodeNode.
     * 
     * @param node
     *            CodeNode for which an index is required
     * @return Index of the specified CodeNode, if that CodeNode exists in the
     *         graph, otherwise it returns -1.
     */
    public abstract int indexOf(CodeNode node);

    /**
     * Determines if a Edge exists between the provided source node and
     * destination node in this DiGraph
     * 
     * @param source
     *            Source CodeNode
     * @param destination
     *            Destination CodeNode
     * @return True if a Edge exists between the Source CodeNode and Destination
     *         CodeNode, false otherwise.
     */
    public abstract boolean isEdge(CodeNode source, CodeNode destination, EdgeType type);

    /**
     * Inserts the specified CodeNode into this graph.
     * 
     * @param source
     *            CodeNode to be inserted.
     */
    public abstract void insert(CodeNode source);

    /**
     * Returns all of the Source Nodes for this graph. Where a Source node is
     * any node which is not associated as the destination end of any edge in
     * the graph.
     * 
     * @return List of all source nodes found in the graph.
     */
    public abstract List<CodeNode> getSources();

    /**
     * Returns all of the Sink Nodes for this graph. Where a Sink node is any
     * node which is not associated as the source end of any edge in the graph.
     * 
     * @return List of all sink nodes found in the graph.
     */
    public abstract List<CodeNode> getSinks();

    /**
     * Returns a set of Nodes representing the difference between this DiGraph
     * and the provided DiGraph.
     * 
     * @param other
     *            DiGraph to compare this graph to
     * @return Set<CodeNode> representing the difference between this DiGraph
     *         and the other DiGraph
     */
    public abstract Set<CodeNode> diff(DiGraph other);
}
